/**
 * 逆波兰表达式主要有以下两个优点：
 *   去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
 *   适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。
 * 
 */

#include <iostream>
#include <vector>
#include <stack>

int cal(int a, int b, char c) {
    int result{};
    switch (c)
    {
    case '+':
        result = a + b;
        break;
    case '-':
        result = a - b;
        break;
    case '*':
        result = a * b;
        break;
    case '/':
        result = a / b;
        break;
    default:
        break;
    }

    return result;
}

int evalRPN(std::vector<std::string>& tokens) {
    std::stack<int> theStack;
    for (int i{}, len = tokens.size(); i < len; i++) {
        std::string o = tokens[i];
        if (o == "+" || o == "-" || o == "*" || o == "/") {
            int a = theStack.top();
            theStack.pop();
            int b = theStack.top();
            theStack.pop();
            theStack.push(cal(b, a, o.at(0)));
        } else {
            theStack.push(atoi(o.c_str()));
        }
    }

    if (theStack.empty()) {
        return 0;
    }
    return theStack.top();
}

int main() {
    std::vector<std::string> tokens { "10","6","9","3","+","-11","*","/","*","17","+","5","+" };
    int result = evalRPN(tokens);
    std::cout << "result: " << result << "\n";

    return 0;
}